#ifndef LIBACCENT_ALGORITHMS_TAKE_HPP
#define LIBACCENT_ALGORITHMS_TAKE_HPP

#include "accent/core.hpp"
#include "accent/utility/safe_position.hpp"
#include "accent/utility/tag_functions.hpp"
#include <cassert>
#include <cstddef>

namespace accent
{

  namespace detail
  {
    template <typename Range>
    class taken
    {
      std::size_t left;
      Range wrapped;

    public:
      using traversal = support::minimum_tag<typename Range::traversal,
                                             forward_traversal_tag>;

      taken(std::size_t n, Range r) : left(n), wrapped(r) {}

      bool empty() const { return left == 0 || wrapped.empty(); }
      void pop_front() {
        assert(left > 0);
        --left;
        wrapped.pop_front();
      }
      auto front() const -> decltype(wrapped.front()) {
        assert(left > 0);
        return wrapped.front();
      }

      class position {
        friend class taken;

        using wrapped = support::safe_position<Range>;
        wrapped pos;
        std::size_t left;

      public:
        position() : pos(), left() {}
        position(wrapped pos, std::size_t left) : pos(pos), left(left) {}

        explicit operator bool() const { return pos && left > 0; }
        bool operator !() const { return !static_cast<bool>(*this); }
        auto operator *() const -> decltype(*pos) {
          assert(left > 0);
          return *pos;
        }
        friend bool operator ==(const position& lhs, const position& rhs) {
          return lhs.pos == rhs.pos && lhs.left == rhs.left;
        }
      };

      position front_position() const {
        return { wrapped.front_position(), left };
      }

      taken from(position p) const {
        assert(p && p.left <= left);
        return { p.left, wrapped.from(p.pos) };
      }

      taken until(position p) const {
        assert(p && p.left <= left);
        return { left - p.left, wrapped.until(p.pos) };
      }
    };

    template <typename Range>
    taken<Range> take_impl(std::size_t n, Range r, single_pass_traversal_tag) {
      return { n, r };
    }

    template <typename Range>
    Range take_impl(std::size_t n, Range r, random_access_traversal_tag) {
      if (n < r.size())
        r.skip_back(r.size() - n);
      return r;
    }
  }

  template <typename Range>
  auto take(std::size_t n, Range r)
    -> decltype(detail::take_impl(n, r, typename Range::traversal()))
  {
    return detail::take_impl(n, r, typename Range::traversal());
  }

}

#endif
